/**
 * \file ArbreAVL.hpp
 * \brief Le code des op�rateurs d'un arbre de recherche.
 * \author Abder
 * \version 1.1, mise à jour des commentaires Thierry
 * \date 2013-11-15
 *
 * Implementation de la classe generique Arbre AVL par cha�nage
 * Arbre represente un arbre binaire de tri. La complexité de
 * la recherche en O(log(n))
 */

#include <algorithm>

namespace tp3
{
/**
 *  \brief Constructeur
 *
 * \post Une instance de la classe Arbre est initialisée
 */
template<typename T, typename V>
ArbreAVL<T,V>::ArbreAVL()
{
   racine = 0;
   nbNoeudsDansArbre = 0;
}

/**
 *  \brief Constructeur de copie
 *
 *  \pre Il faut qu'il y ait suffisamment de mémoire
 *  \post une copie profonde de l'arbre source est instanciée
 *  \exception bad_alloc s'il n'y a pas assez de mémoire
 *
 * \param[in] source L'arbre source
 */
template<typename T, typename V>
ArbreAVL<T,V>::ArbreAVL(const ArbreAVL& source) throw (std::bad_alloc)
{
   _auxCopier(source.racine, racine);
   nbNoeudsDansArbre = source.nbNoeudsDansArbre;
}

/**
 *  \brief Destructeur
 *
 *  \post l'instance de Graphe est détruite
 */
template<typename T, typename V>
ArbreAVL<T,V>::~ArbreAVL()
{
   _auxDetruire(racine);
}

/**
 *  \brief Détruire un sous-arbre
 *
 * \post Le sous-arbre est détruit
 * \param[in] aDetruire Le sous-arbre à détruire
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxDetruire(Noeud * &aDetruire)
{
   if (aDetruire != 0)
   {
      _auxDetruire(aDetruire->gauche);
      _auxDetruire(aDetruire->droite);
      delete aDetruire;
      nbNoeudsDansArbre--;
      aDetruire = 0;
   }
}

/**
 * \brief Surcharger l'opérateur ==
 *
 * \post Les 2 opérandes (arbres) sont inchangés
 * \param[in] a Un arbre, second op�rande dans la comparaison
 * \return true ou false
 */
template<typename T, typename V>
bool ArbreAVL<T,V>::operator ==(const ArbreAVL &a)
{
   return (_auxArbresEgaux(racine, a.racine));
}

/**
 * \brief Surcharger l'opérateur =
 *
 * \pre Il y a assez de mémoire pour l'opération
 * \post Une copie d'un arbre est retournée
 * \exception bad_alloc si la mémoire est insuffisante
 * \param[in] a Un arbre, le membre de droite dans l'affectation
 * \return Une copie de l'arbre courant
 */
template<typename T, typename V>
const ArbreAVL<T,V>& ArbreAVL<T,V>::operator =(const ArbreAVL & a) throw (std::bad_alloc)
{
   _auxDetruire(racine);
   _auxCopier(a.racine, racine);
   nbNoeudsDansArbre = a.nbNoeudsDansArbre;

   return (*this);
}

/**
 *  \brief Vérifier si l'arbre est vide
 *
 * \post L'arbre est inchangé
 * \return true ou false
 */
template<typename T, typename V>
bool ArbreAVL<T,V>::estVide() const
{
   return nbNoeudsDansArbre == 0;
}

/**
 *  \brief Retourner le nombre d'éléments dans l'arbre
 *
 * \post L'arbre est inchangé
 * \return Le nombre d'éléments dans l'arbre
 */
template<typename T, typename V>
long ArbreAVL<T,V>::taille() const
{
   return nbNoeudsDansArbre;
}

/**
 *  \brief Retourner la hauteur de l'arbre
 *
 * La détermination de la hauteur se fait par parcours de l'arbre
 *
 * \pre L'arbre n'est pas vide
 * \post L'arbre est inchangé
 * \exception logic_error si l'arbre est vide
 * \return La hauteur de l'arbre
 */
template<typename T, typename V>
int ArbreAVL<T,V>::hauteur() const throw (std::logic_error)
{
   if (nbNoeudsDansArbre == 0)
      throw std::logic_error("hauteur: l'arbre est vide!\n");

   return _hauteurParcours(racine);
}

/**
 *  \brief Retourner la hauteur d'un sous-arbre
 *
 * Fonction auxiliaire (récursive)
 *
 * \post Le sous-arbre est inchangé
 * \param[in] arb L'adresse du noeud racine du sous-arbre en entrée
 * \return La hauteur du sous-arbre
 */
template<typename T, typename V>
int ArbreAVL<T,V>::_hauteurParcours(Noeud * arb) const
{
   if (arb == 0)
      return -1;

   return 1 + std::max(_hauteurParcours(arb->gauche), _hauteurParcours(arb->droite));
}

/**
 *  \brief Retourner la valeur maximum dans l'arbre
 *
 * \pre L'arbre n'est pas vide
 * \post L'arbre est inchangé
 * \exception logic_error si l'arbre est vide
 * \return E- Le maximum dans l'arbre
 */
template<typename T, typename V>
const T& ArbreAVL<T,V>::max() const throw (std::logic_error)
{
   return _max(racine);
}

/**
 *  \brief Retourner la valeur maximum dans un sous-arbre
 *
 * Fonction auxiliaire (récursive)
 *
 * \pre Le sous-arbre n'est pas vide
 * \post Le sous-arbre est inchangé
 * \exception logic_error si le sous-arbre est vide
 * \param[in] sousArbre L'adresse du noeud racine du sous-arbre en entrée
 * \return T Le maximum dans le sous-arbre
 */
template<typename T, typename V>
const T & ArbreAVL<T,V>::_max(Noeud*sousArbre) const throw (std::logic_error)
{
   if (sousArbre == 0)
      throw std::logic_error("max: l'arbre (sous-arbre) est vide!\n");

   if (sousArbre->droite == 0)
   {
      return sousArbre->info;
   }

   return _max(sousArbre->droite);
}

/**
 *  \brief Retourner la valeur minimum dans l'arbre
 *
 * \pre L'arbre n'est pas vide
 * \post L'arbre est inchangé
 * \exception logic_error si l'arbre est vide
 * \return E- Le minimum dans l'arbre
 */
template<typename T, typename V>
const T& ArbreAVL<T,V>::min() const throw (std::logic_error)
{
   if (nbNoeudsDansArbre == 0)
      throw std::logic_error("min: l'arbre est vide!\n");

   if (racine->gauche == 0)
   {
      return racine->info;
   }

   Noeud * temp = racine->gauche;
   while (temp->gauche != 0)
      temp = temp->gauche;

   return temp->info;
}

/**
 *  \brief Retourner la valeur minimum dans un sous-arbre
 *
 * Fonction auxiliaire (récursive)
 *
 * \pre Le sous-arbre n'est pas vide
 * \post Le sous-arbre est inchangé
 * \exception logic_error si le sous-arbre est vide
 * \param[in] sousArbre L'adresse du noeud racine du sous-arbre en entrée
 * \return T Le minimum dans le sous-arbre
 */
template<typename T, typename V>
const T& ArbreAVL<T,V>::_min(Noeud*sousArbre) const throw (std::logic_error)
{
   if (sousArbre == 0)
      throw std::logic_error("min: l'arbre (sous-arbre) est vide!\n");

   if (sousArbre->gauche == 0)
   {
      return sousArbre->info;
   }

   return _min(sousArbre->gauche);
}

/**
 *  \brief Retourner le nombre de feuilles dans l'arbre
 *
 * \post Le graphe est inchangé
 * \return Le nombre de feuilles dans l'arbre
 */
template<typename T, typename V>
int ArbreAVL<T,V>::nbFeuilles() const
{
   return _nbFeuilles(racine);
}

/**
 *  \brief Retourner le nombre de feuilles dans un sous-arbre
 *
 * Fonction auxiliaire (récursive)
 * \post Le sous-arbre est inchangé
 * \param[in] sousArbre L'adresse du noeud racine du sous-arbre en entrée
 * \return Le nombre de feuilles dans le sous-arbre
 */
template<typename T, typename V>
int ArbreAVL<T,V>::_nbFeuilles(Noeud*sousArbre) const
{
   int nbG(0), nbD(0);

   // le noeud courant existe (c-a-d n'est pas NULL)
   if (sousArbre != 0)
   {
      //est une feuille si droit et gauche sont NULL retourner 1
      if (sousArbre->gauche == 0 && sousArbre->droite == 0)
      {
         return 1;
      }
      // n'est pas une feuille, droit ou gauche n'est pas NULL
      else
      {
         if (sousArbre->gauche != 0)
            nbG = _nbFeuilles(sousArbre->gauche);

         if (sousArbre->droite != 0)
            nbD = _nbFeuilles(sousArbre->droite);
      }
   }

   return nbG + nbD;
}

/**
 *  \brief Retourner le nombre d'éléments dans l'arbre
 *
 * L'algorithme fait un parcours de l'Arbre pour compter
 *
 * \post L'arbre est inchangé
 * \return Le nombre de noeuds dans l'arbre
 */
template<typename T, typename V>
int ArbreAVL<T,V>::compterNbNoeuds() const
{
   return _nbNoeuds(racine);
}

/**
 *  \brief Retourner le nombre d'éléments dans un sous-arbre
 *
 * Fonction auxiliaire (récursive)
 * \post Le sous-arbre est inchangé
 * \return Le nombre de noeuds dans le sous-arbre
 */
template<typename T, typename V>
int ArbreAVL<T,V>::_nbNoeuds(Noeud* arb) const
{
   if (arb == 0)
      return 0;

   return _nbNoeuds(arb->gauche) + _nbNoeuds(arb->droite) + 1;
}

/**
 * \brief Retourner le parent d'un élément dans l'arbre
 * \pre L'arbre n'est pas vide
 * \pre L'élément fait partie de l'arbre
 * \post L'arbre est inchangé
 * \exception logic_error si l'arbre est vide
 * \exception logic_error si l'élément n'est pas dans l'arbre
 * \param[in] elementRecherche l'élément dont on cherche le parent
 * \return T Le parent de T dans l'arbre
 */
template<typename T, typename V>
const T& ArbreAVL<T,V>::parent(const T& elementRecherche) const
{
   Noeud* noeudDeEl = _auxAppartient(racine, elementRecherche);
   Noeud* parentDeEl = _parent(racine, noeudDeEl);

   return parentDeEl->info;
}

/**
 *  \brief Retourner le parent d'un élément dans sous-arbre
 *
 * Fonction auxiliaire (récursive)
 *
 * \pre Le sous-arbre n'est pas vide
 * \pre L'élément fait partie du sous-arbre
 * \post L'arbre est inchangé
 * \exception logic_error si le sous-arbre est vide
 * \exception logic_error si l'élément n'est pas dans le sous-arbre
 * \param[in] sousArbreRecherche L'adresse du sous-arbre dans lequel on effectue la recherche du parent
 * \param[in] filsDuNoeudCherche L'adresse du noeud dont on cherche son parent
 *
 * \return L'adresse du noeud parent
 */
template<typename T, typename V>
typename ArbreAVL<T,V>::Noeud* ArbreAVL<T,V>::_parent(Noeud* sousArbreRecherche,
      Noeud* filsDuNoeudCherche) const throw (std::logic_error)
{
   if (sousArbreRecherche == 0)
      throw std::logic_error("parent: l'arbre est vide!\n");

   if (filsDuNoeudCherche == 0)
      throw std::logic_error("parent: l'element dont on cherche son parent n'existe pas!\n");

   if (filsDuNoeudCherche == sousArbreRecherche)
      throw std::logic_error("parent: Le parent de la racine d'existe pas!\n");

   if (filsDuNoeudCherche->info < sousArbreRecherche->info)
   {
      if (sousArbreRecherche->gauche == filsDuNoeudCherche)
      {
         return sousArbreRecherche;
      }
      else
      {
         return _parent(sousArbreRecherche->gauche, filsDuNoeudCherche);
      }
   }
   else
   {
      if (sousArbreRecherche->droite == filsDuNoeudCherche)
      {
         return sousArbreRecherche;
      }
      else
      {
         return _parent(sousArbreRecherche->droite, filsDuNoeudCherche);
      }
   }
}

/**
 *  \brief Retourner le successeur d'un élément dans l'arbre
 *
 * \pre L'arbre n'est pas vide
 * \pre L'élément fait partie de l'arbre
 * \pre L'éléement n'est pas le maximum dans l'arbre
 * \post L'arbre est inchangé
 * \exception logic_error si l'arbre est vide
 * \exception logic_error si l'élément n'est pas dans l'arbre
 * \exception logic_error si l'élément est le maximum dans l'arbre
 * \param[in] info La donnée dont on cherche son successeur
 * \return E- Le successeur de info dans l'arbre
 */
template<typename T, typename V>
T ArbreAVL<T,V>::successeur(const T& info) const throw (std::logic_error)
{
   return _successeur(racine, info);
}

/**
 *  \brief Retourner le successeur d'un élément dans un sous-arbre
 *
 *  Fonction auxiliaire (récursive)
 *
 * \pre Le sous-arbre n'est pas vide
 * \pre L'élément fait partie du sous-arbre
 * \pre L'élément n'est pas le maximum dans le sous-arbre
 * \post Le sous-arbre est inchangé
 * \exception logic_error si le sous-arbre est vide
 * \exception logic_error si l'élément n'est pas dans le sous-arbre
 * \exception logic_error si l'élément est le maximum dans le sous-arbre
 * \param[in] arb Le sous-arbre dans lequel on cherche le successeur
 * \param[in] info La donnée dont on cherche son successeur
 *
 * \return E- Le successeur de info
 */
template<typename T, typename V>
T ArbreAVL<T,V>::_successeur(Noeud* arb, const T& info) const throw (std::logic_error)
{
   if (nbNoeudsDansArbre == 0)
      throw std::logic_error("successeur: l'arbre est vide!\n");

   Noeud* sArb = _auxAppartient(racine, info);

   if (sArb == 0)
      throw std::logic_error(
            "successeur: l'element dont on cherche son successeur n'existe pas!\n");

   if (info == _max(arb))
      throw std::logic_error(
            "successeur: l'element est le max dans l'arbre, il n'a pas de successeur!\n");

   if (sArb->droite != 0)
   {
      return _min(sArb->droite);
   }
   else
   {
      Noeud * pere = _parent(arb, sArb);
      while (pere->info < sArb->info)
      {
         pere = _parent(arb, pere);
      }

      return pere->info;
   }
}

/**
 *  \brief Lister un arbre
 *
 * Le listage se fait dans un tableau, l'appelant doit intialiser le tableau
 *
 * \post L'arbre est inchangé
 * \param[out] res Le tableau qui contient le listage de l'arbre
 * \param[out] ind La cardinalité du tableau
 */
template<typename T, typename V>
void ArbreAVL<T,V>::lister(T* res, int&ind) const
{
   _auxEnOrdre(racine, res, ind);
}

/**
 *  \brief Parcourir en En-Ordre un sous-arbre
 *
 * Fonction auxiliaire. Cas d'un tableau en argument.
 * \post Le sous-arbre est inchangé
 * \param[in] arb Le sous-arbre à parcourir
 * \param[out] res Le tableau qui contient le listage du sous-arbre
 * \param[out] ind La cardinalité du tableau
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxEnOrdre(Noeud* arb, T* res, int&ind) const
{
   if (arb == 0)
      return;
   else
   {
      _auxEnOrdre(arb->gauche, res, ind);

      /* traitement(arb)  */
      res[ind] = arb->info;
      ind++;

      _auxEnOrdre(arb->droite, res, ind);
   }
}

/**
 *  \brief Lister un arbre
 *
 * Le listage se fait dans un vector
 *
 * \pre Il y a assez de mémoire
 * \post L'arbre est inchangé
 * \exception bad_alloc s'il n'y a pas assez de mémoire
 * \return Le vector qui contient le listage de l'arbre
 */
template<typename T, typename V>
std::vector<std::pair<T, V > > ArbreAVL<T,V>::lister() const throw (std::bad_alloc)
{
   std::vector<std::pair<T, V > > v;
   _auxEnOrdre(racine, v);
   return v;
}

/**
 *  \brief Parcourir en En-Ordre un sous-arbre
 *
 * Fonction auxiliaire. Cas d'un vector en argument.
 * \post Le sous-arbre est inchangé
 * \param[in] arb Le sous-arbre à parcourir
 * \param[out] v Le vector qui contient le listage du sous-arbre
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxEnOrdre(Noeud* arb, std::vector<std::pair<T, V > >& v) const
{
   if (arb == 0)
      return;
   else
   {
      _auxEnOrdre(arb->gauche, v);

      /* traitement(arb)  */
   	  std::pair<T,V> p(arb->info, arb->value);
      v.push_back(p);

      _auxEnOrdre(arb->droite, v);
   }
}

/**
 *  \brief Copier deux sous-arbre
 *
 * Fonction auxiliaire.
 *
 * \post Le sous-arbre source est inchangé
 * \param[in] source Le sous-arbre à copier
 * \param[out] destination La copie
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxCopier(Noeud * source, Noeud * & destination) throw (std::bad_alloc)
{
   if (source != 0)
   {
      destination = new Noeud(source->info, source->value);
      destination->hauteur = source->hauteur;
      _auxCopier(source->gauche, destination->gauche);
      _auxCopier(source->droite, destination->droite);
   }
   else
      destination = 0;
}

/**
 *  \brief Insérer un élément dans l'arbre (AVL)
 *
 * Insertion dans l'ordre de tri et avec balancement
 *
 * \pre Il y a assez de mémoire
 * \post L'arbre contient un élément de plus
 * \exception bad_alloc s'il n'y a pas assez de mémoire
 * \param[in] element La donnée à inserer dans l'arbre AVL
 */
template<typename T, typename V>
void ArbreAVL<T,V>::inserer(const T& element, const V& value) throw (std::bad_alloc)
{
   _auxInserer(racine, element, value);
}

/**
 *  \brief Insérer élément dans un sous-arbre
 *
 * Fonction auxiliaire (récursive). Insertion avec balancement
 *
 * \post Le sous-arbre contient un élément de plus
 * \param[in] sousArbre Le sous-arbre dans lequel on insert
 * \param[in] infoAInserer La donnée à insérer dans l'arbre
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxInserer(Noeud *&sousArbre, const T &infoAInserer, const V &valueInserer) throw (std::bad_alloc)
{
   if (sousArbre == 0)
   {
      sousArbre = new Noeud(infoAInserer, valueInserer);
      nbNoeudsDansArbre++;
      return;
   }
   //Inserer à gauche si elementAInserver est plus petit que le noeud courant
   if (sousArbre->info > infoAInserer)
   {
      _auxInserer(sousArbre->gauche, infoAInserer, valueInserer);
      if ((_hauteur(sousArbre->gauche) - _hauteur(sousArbre->droite)) == 2)
      {
         if (sousArbre->gauche->info > infoAInserer)
            _zigZigGauche(sousArbre);
         else
            _zigZagGauche(sousArbre);
      }
      else
      {
         sousArbre->hauteur = 1
               + std::max(_hauteur(sousArbre->gauche), _hauteur(sousArbre->droite));
      }
   }
   //Inserer à droite si elementAInserver est plus grand ou egal que le noeud courant
   else
   {
      _auxInserer(sousArbre->droite, infoAInserer, valueInserer);
      if ((_hauteur(sousArbre->droite) - _hauteur(sousArbre->gauche)) == 2)
      {
         if (sousArbre->droite->info <= infoAInserer) //= pour le cas d'un doublon
         {
            _zigZigDroit(sousArbre);
         }
         else
         {
            _zigZagDroit(sousArbre);
         }
      }
      else
      {
         sousArbre->hauteur = 1
               + std::max(_hauteur(sousArbre->droite), _hauteur(sousArbre->gauche));
      }
   }
}

/**
 *  \brief Simple rotation - Déséquilibre gauche-gauche
 *
 * \post Le sous-arbre sous-tendu par le noeud critique est balancé
 * \param[in, out] noeudCritique Le noeud critique
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_zigZigGauche(Noeud * &noeudCritique)
{
   Noeud *K1;

   K1 = noeudCritique->gauche;
   noeudCritique->gauche = K1->droite;
   K1->droite = noeudCritique;
   noeudCritique->hauteur = 1
         + std::max(_hauteur(noeudCritique->gauche), _hauteur(noeudCritique->droite));
   K1->hauteur = 1 + std::max(_hauteur(K1->gauche), noeudCritique->hauteur);

   noeudCritique = K1;
}

/**
 *  \brief Simple rotation - Déséquilibre droite-droite
 *
 * \post Le sous-arbre sous-tendu par le noeud critique est balancé
 * \param[in, out] noeudCritique Le noeud critique
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_zigZigDroit(Noeud * &noeudCritique)
{
   Noeud *K1;

   K1 = noeudCritique->droite;
   noeudCritique->droite = K1->gauche;
   K1->gauche = noeudCritique;
   noeudCritique->hauteur = 1
         + std::max(_hauteur(noeudCritique->droite), _hauteur(noeudCritique->gauche));
   K1->hauteur = 1 + std::max(_hauteur(K1->droite), noeudCritique->hauteur);
   noeudCritique = K1;
}

/**
 *  \brief Double rotation - Déséquilibre gauche-droite
 *
 * \post Le sous-arbre sous-tendu par le noeud critique est balancé
 * \param[in, out] noeudCritique Le noeud critique
 *
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_zigZagGauche(Noeud *&noeudCritique)
{
   _zigZigDroit(noeudCritique->gauche);
   _zigZigGauche(noeudCritique);
}

/**
 *  \brief Double rotation - Déséquilibre droite-gauche
 *
 * \post Le sous-arbre sous-tendu par le noeud critique est balancé
 * \param[in, out] noeudCritique Le noeud critique
 *
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_zigZagDroit(Noeud *& noeudCritique)
{
   _zigZigGauche(noeudCritique->droite);
   _zigZigDroit(noeudCritique);
}

/**
 *  \brief Retourner la hauteur d'un noeud
 * \param[in] arb L'adresse du noeud dont on desire sa hauteur
 * \return La hauteur de arb
 */
template<typename T, typename V>
int ArbreAVL<T,V>::_hauteur(Noeud *arb) const
{
   if (arb == 0)
      return -1;
   return arb->hauteur;
}

/**
 *  \brief Enlever un élément dans l'arbre AVL
 * L'arbre n'est pas balancé aprés la suppression
 *
 * \pre L'arbre n'est pas vide
 * \pre L'élément fait partie de l'arbre
 * \post L'arbre contient un élément de moins
 * \exception logic_error si l'arbre est vide
 * \exception logic_error si l'élément n'est pas dans l'arbre
 * \param[in] data La donnée à enlever de l'arbre
 */
template<typename T, typename V>
void ArbreAVL<T,V>::enlever(const T& data) throw (std::logic_error)
{
   if (racine == 0)
      throw std::logic_error("enlever: l'arbre est vide\n");

   if (_auxAppartient(racine, data) == 0)
      throw std::logic_error("enlever: l'element ne fait pas partie de l'arbre\n");

   _auxEnlever(racine, data); //data est certain dans l'arbre
}

/**
 *  \brief Enlever un élément dans un sous-arbre
 *
 * Fonction auxiliaire (récursive). La fonction ne balance pas aprés la suppression.
 *
 * \post Le sous-arbre contient un élément de moins
 * \param[in] t Le sous-arbre dans lequel on fait l'enlèvement
 * \param[in] valeur La donnée à enlever du sous-arbre
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxEnlever(Noeud * & t, const T & valeur)
{
   if (t->info > valeur)
      _auxEnlever(t->gauche, valeur);

   else if (t->info < valeur)
      _auxEnlever(t->droite, valeur);

   // si on se rend jusqu'ici, c'est qu'on a trouvé le noeud
   // qui contient la valeur recherchée
   else if (t->gauche != 0 && t->droite != 0)
   {
      // deux enfants: il faut trouver la valeur suivante dans la
      // séquence et la mettre à la place de la valeur du noeud actuel.

      //chercher le noeud qui contient la valeur minimale dans le sous-arbre de droite
      Noeud * temp = t->droite;
      while (temp->gauche != 0)
         temp = temp->gauche;
      t->info = temp->info;
      _auxRetireMin(t->droite); // Retirer minimum dans le sous-arbre droit
   }
   else
   {
      // le noeud n'a aucun enfant ou qu'un seul enfant, il suffit donc de retirer
      // ce noeud et pointer sur l'éventuel enfant
      Noeud * vieuxNoeud = t;
      t = (t->gauche != 0) ? t->gauche : t->droite;
      delete vieuxNoeud;
      nbNoeudsDansArbre--;
   }
}

/**
 *  \brief Enlever l'élément minimum dans un sous-arbre
 *
 * Fonction auxiliaire (récursive).
 *
 * \post Le sous-arbre contient un élément de moins
 * \param[in] t Le sous-arbre dans lequel on fait l'enl�vement
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxRetireMin(Noeud* & t)
{
   if (t == 0)
      throw std::logic_error("_auxRetireMin: probleme pointeur NULL\n");
   else if (t->gauche != 0)
      _auxRetireMin(t->gauche);
   else
   {
      Noeud * tmp = t;
      t = t->droite;
      delete tmp;
      nbNoeudsDansArbre--;
   }
}

/**
 *  \brief Vérifier si un élément  est dans l'arbre
 *
 * \post L'arbre est inchangé
 * \param[in] data L'élément recherché dans l'arbre
 * \return VRAI si data fait partie de l'arbre, FAUX sinon
 */
template<typename T, typename V>
bool ArbreAVL<T,V>::appartient(const T &data) const
{
   return _auxAppartient(racine, data) != 0;
}

/**
 *  \brief Chercher un élément dans un sous-arbre
 *
 * Fonction auxiliaire (récursive).
 *
 * \post Le sous-arbre est inchangé
 * \param[in] arbre Le sous-arbre dans lequel on effectue la recherche
 * \param[in] data L'élément recherché dans le sous-arbre
 * \return L'adresse du noeud contenant data, NULL si data ne fait pas partie de l'arbre
 */
template<typename T, typename V>
typename ArbreAVL<T,V>::Noeud* ArbreAVL<T,V>::_auxAppartient(Noeud* arbre, const T &data) const
{
   if (arbre == 0)
   {
      return 0;
   }
   if (arbre->info == data)
   {
      return arbre;
   }

   if (arbre->info > data)
   {
      return _auxAppartient(arbre->gauche, data);
   }
   else
   {
      return _auxAppartient(arbre->droite, data);
   }

}

/**
 *  \brief Parcourir en Pré-Ordre un arbre
 *
 * \post L'arbre est inchangé
 * \param[in] traitement La fonction de traitement lors du parcours
 */
template<typename T, typename V>
void ArbreAVL<T,V>::parcourirPreOrdre(void (*traitement)(T &iteme)) const
{
   _auxPreOrdre(racine, traitement);
}

/**
 *  \brief Parcourir en Pre-Ordre un sous-arbre
 *
 * Fonction auxiliaire
 *
 * \post Le sous-arbre est inchangé
 * \param[in] arbre Le sous-arbre à parcourir
 * \param[in] traitement La fonction de traitement lors du parcours
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxPreOrdre(Noeud * arbre, void (*traitement)(T &iteme)) const
{
   if (arbre != 0)
   {
      traitement(arbre->info);
      _auxPreOrdre(arbre->gauche, traitement);
      _auxPreOrdre(arbre->droite, traitement);
   }
}

/**
 *  \brief Parcourir en Pre-Ordre un sous-arbre
 *
 * Fonction auxiliaire. Cas d'un vector en argument.
 * \post Le sous-arbre est inchangé
 * \param[in] arb Le sous-arbre à parcourir
 * \param[out] v Le vector qui contient le listage du sous-arbre
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxPreOrdre(Noeud* arb, std::vector<std::pair<T, V > >& v) const
{
   if (arb == 0)
      return;
   else
   {
	  std::pair<T,V> p(arb->info, arb->value);
      v.push_back(p);
      _auxPreOrdre(arb->gauche, v);
      _auxPreOrdre(arb->droite, v);
   }
}

/**
 *  \brief Parcourir en En-Ordre un arbre
 *
 * \post L'arbre est inchangé
 * \param[in] traitement La fonction de traitement lors du parcours
 */
template<typename T, typename V>
void ArbreAVL<T,V>::parcourirEnOrdre(void (*traitement)(T &iteme)) const
{
   _auxEnOrdre(racine, traitement);
}

/**
 *  \brief Parcourir en En-Ordre un sous-arbre
 *
 * Fonction auxiliaire
 *
 * \post Le sous-arbre est inchangé
 * \param[in] arbre Le sous-arbre à parcourir
 * \param[in] traitement La fonction de traitement lors du parcours
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxEnOrdre(Noeud *arbre, void (*traitement)(T &iteme)) const
{
   if (arbre != 0)
   {
      _auxEnOrdre(arbre->gauche, traitement);
      traitement(arbre->info);
      _auxEnOrdre(arbre->droite, traitement);
   }
}

/**
 *  \brief Parcourir en Post-Ordre un arbre
 *
 * \post L'arbre est inchangé
 * \param[in] traitement La fonction de traitement lors du parcours
 */
template<typename T, typename V>
void ArbreAVL<T,V>::parcourirPostOrdre(void (*traitement)(T &iteme)) const
{
   _auxPostOrdre(racine, traitement);
}

/**
 *  \brief Parcourir en Post-Ordre un sous-arbre
 *
 * Fonction auxiliaire
 *
 * \post Le sous-arbre est inchangé
 * \param[in] arbre Le sous-arbre à parcourir
 * \param[in] traitement La fonction de traitement lors du parcours
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxPostOrdre(Noeud *arbre, void (*traitement)(T &iteme)) const
{
   if (arbre != 0)
   {
      _auxPostOrdre(arbre->gauche, traitement);
      _auxPostOrdre(arbre->droite, traitement);
      traitement(arbre->info);
   }
}

/**
 *  \brief Parcourir en Post-Ordre un sous-arbre
 *
 * Fonction auxiliaire. Cas d'un vector en argument.
 * \post Le sous-arbre est inchangé
 * \param[in] arb Le sous-arbre à parcourir
 * \param[out] v Le vector qui contient le listage du sous-arbre
 */
template<typename T, typename V>
void ArbreAVL<T,V>::_auxPostOrdre(Noeud* arb, std::vector<std::pair<T, V > >& v) const
{
   if (arb == 0)
      return;
   else
   {
      _auxPreOrdre(arb->gauche, v);
      _auxPreOrdre(arb->droite, v);
      v.push_back(arb->info);
   }
}

/**
 *  \brief Parcourir en Pre-Ordre un sous-arbre
 *
 * Fonction auxiliaire
 *
 * \post Le sous-arbre est inchangé
 * \return un vecteur contenant les noeuds dans l'ordre
 */
template<typename T, typename V>
std::vector<std::pair<T, V > > ArbreAVL<T,V>::listerPreOrdre() const
{
   std::vector<std::pair<T, V > > v;
   _auxPreOrdre(racine, v);
   return v;
}

/**
 *  \brief Parcourir en ordre un sous-arbre
 *
 * Fonction auxiliaire
 *
 * \post Le sous-arbre est inchangé
 * \return un vecteur contenant les noeuds dans l'ordre
 */
template<typename T, typename V>
std::vector<std::pair<T, V > > ArbreAVL<T,V>::listerEnOrdre() const
{
   std::vector<std::pair<T, V > > v;
   _auxEnOrdre(racine, v);
   return v;
}

/**
 *  \brief Parcourir en Post-Ordre un sous-arbre
 * Fonction auxiliaire
 * \post Le sous-arbre est inchangé
 * \return un vecteur contenant les noeuds dans l'ordre
 */
template<typename T, typename V>
std::vector<std::pair<T, V > > ArbreAVL<T,V>::listerPostOrdre() const
{
   std::vector<std::pair<T, V > > v;
   _auxPostOrdre(racine, v);
   return v;
}

/**
 *  \brief Parcourir un arbre par niveau
 *
 * \post L'arbre est inchangé
 * \param[in] traitement La fonction de traitement lors du parcours
 */
template<typename T, typename V>
void ArbreAVL<T,V>::parcourirParNiveau(void (*traitement)(T &iteme)) const
{
   std::queue<Noeud*> Q;
   Noeud * temp;

   Q.push(racine);
   while (!Q.empty())
   {
      temp = Q.front();
      traitement(temp->info);
      Q.pop();
      if (temp->gauche != 0)
         Q.push(temp->gauche);
      if (temp->droite != 0)
         Q.push(temp->droite);
   }
}

/**
 *  \brief Vérifier si 2 sous-arbres sont égaux
 *
 * \post Les 2 sous-arbres sont inchangés
 * \param[in] premier Le premier sous-arbre de la comparaison
 * \param[in] second Le second sous-arbre de la comparaison
 * \return VRAI si les 2 arbres sont identiques, FAUX sinon
 */
template<typename T, typename V>
bool ArbreAVL<T,V>::_auxArbresEgaux(Noeud * premier, Noeud * second)
{
   if ((premier == 0) && (second == 0))
      return (true);
   else if ((premier != 0) && (second != 0))
      return ((premier->info == second->info) && _auxArbresEgaux(premier->gauche, second->gauche)
            && _auxArbresEgaux(premier->droite, second->droite));
   else
      return (false);
}

}
